package euler.p051_100;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import euler.MainEuler;

public class Euler095 extends MainEuler {

    /*
        The proper divisors of a number are all the divisors
        excluding the number itself.
        For example, the proper divisors of 28 are 1, 2, 4, 7, and 14.
        As the sum of these divisors is equal to 28, we call it a perfect
        number.

        Interestingly the sum of the proper divisors of 220 is 284 and
        the sum of the proper divisors of 284 is 220, forming a chain of
        two numbers. For this reason, 220 and 284 are called an amicable pair.

        Perhaps less well known are longer chains.
        For example, starting with 12496, we form a chain of five numbers:

        12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

        Since this chain returns to its starting point,
        it is called an amicable chain.

        Find the smallest member of the longest amicable chain
        with no element exceeding one million.

     */
    public String resolve() {
        int limite = 1000000;
        boolean[] array = new boolean[limite];
        int minimo = 0;
        int largoMaximo = 0;

        for (int i = 2; i < limite; i++) {
            array[i] = true;
            Set<Integer> cadena = new HashSet<Integer>();
            int n = i;

            while ((n < limite) && (n==i || !array[n]) && !cadena.contains(n) && (n != 1)) {

                cadena.add(n);
                int suma = -n;
                List<Integer> divisores = primeHelper.divisores(n);

                for (Integer divisor: divisores) {
                    suma+=divisor;
                }

                n = suma;

                if (n >= limite) {
                    for (Integer j: cadena) {
                        array[j] = true;
                    }
                    cadena.clear();
                }
            }

            if (n == i) {
                for (Integer j: cadena) {
                    array[j] = true;
                }

                if (cadena.size() > largoMaximo) {
                    largoMaximo = cadena.size();
                    minimo = i;
                }
            }

        }

        return String.valueOf(minimo);
        // 14316
    }

}
